import math
from typing import Optional, List
from icecream import ic


class MyQueue():
    def __init__(self):
        self.queue = []

    def pop(self, x):
        if self.queue and self.queue[0] == x:
            self.queue.pop(0)

    def push(self, x):
        if self.queue and self.queue[0] < x:
            self.queue = [x]
        else:
            while self.queue and self.queue[-1] < x:
                self.queue.pop()
            self.queue.append(x)

    def first(self):
        return self.queue[0]


class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < k:
            return [max(nums)]
        result = []
        mydeque = MyQueue()
        for i in range(k):
            mydeque.push(nums[i])
        result.append(mydeque.first())

        for i in range(0, len(nums) - k):
            mydeque.pop(nums[i])
            mydeque.push(nums[i + k])

            result.append(mydeque.first())
        return result


so = Solution()
print('结果是', so.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
